1. Field of the Invention
The present invention relates to computer networks, and deals more particularly with methods, systems, and computer program products for improving the connectivity between nodes in multiple topology subnets by using a common connection network (such as the public Internet).
2. Description of the Related Art
For purposes of the following descriptions, a computer data network (or, equivalently, a computer communications network) can be defined generally as a collection of nodes and the communications links which connect various ones of the nodes to each other. Nodes may be general purpose computers or special purpose computers such as routers. Nodes may also be terminal devices such as printers or display devices. Links are generally connected to nodes on either end by “adapters”. For example, a node may connect to a token ring local area network (“LAN”) using a token ring adapter, and/or may connect to an Ethernet LAN using an Ethernet adapter. Collectively, the nodes and links between them are referred to as network resources. The physical configuration and characteristics of the various nodes and links in a network are said to be the topology of the network.
To transmit data from one node to another node, a path or route must be set up through the network. The route will include the originating node, the destination node, possibly one or more intermediate nodes, and the links or transmission groups which connect the nodes on the route. A transmission group or “TG”, as the term is used herein, refers to a set of parallel links with similar characteristics, which may be combined as a single logical link with a higher aggregated capacity. (A transmission group may alternatively comprise only a single link. The terms “link” and “transmission group” are used interchangeably hereinafter.) Links between nodes may use any one of a number of types of transmission media, and may be permanent in nature (such as conventional cable connections) or may be enabled only when needed (such as dial-up telephone connections).
Those nodes which are capable of performing functions within the network, including routing of messages between the node itself and its adjacent or neighboring nodes, selection of routes for messages to be transmitted between two nodes, and the furnishing of directory services for other nodes, are referred to herein as “network nodes”. Nodes which do not provide these types of functions are referred to herein as “end nodes”. End nodes may host application programs, but require the services of network nodes to locate partner programs in the network and set up communications. Border nodes which combine the function of a network node and an end node were disclosed in commonly-assigned U.S. Pat. No. 5,241,682, which is entitled “Border Node having Routing and Functional Capability in a First Network and Only Local Address Capability in a Second Network” (hereinafter referred to as “the border node patent”), which is hereby incorporated herein by reference as if set forth fully. Border nodes enable communication between two (or more) networks, and have a network node interface for outbound communications from the native (e.g. originating node's) network and an end node interface for inbound communications from the non-native (e.g. destination node's) network.
To transmit data effectively through a network, the nodes cooperate with each other on the implementation of various distributed communication protocols. Some of the more important protocols are a location protocol, which is used to find the destination node which implements a desired application program, and a routing protocol, which is used to select an appropriate route or path through the network on which to transmit the data. Typically, the selected route is optimized in some sense. While there are many techniques for route optimization, most involve minimizing the number of nodes and links in the path. One example is the “Open Shortest Path First”, or “OSPF”, routing protocol. OSPF is defined in Request For Comments (“RFC”) 2178, “OSPF Version 2” (July 1997), from the Internet Engineering Task Force (“IETF”). Another routing protocol is the Routing Information Protocol, or “RIP”, which is defined in RFC 1723, “RIP Version 2” (November 1994). OSPF and RIP are commonly used for routing in Transmission Control Protocol/Internet Protocol (“TCP/IP”) networks, and are well known in the art.
Layered network architectures are common. One example is the Systems Network Architecture (“SNA”) which was defined by the International Business Machines Corporation (“IBM”). Another example is the Open Systems Interconnection (“OSI”) reference model, which is defined in International Standard ISO/IEC 7498-1 (1994), “Open Systems Interconnection—Basic Reference Model”. These layered network architectures are comprised of a physical layer at the lowest layer, where the actual data transmission over physical media occurs, and a highest layer where transmitted and received data is abstracted for use by an application program. Different layered architectures use different numbers of intermediate layers and different functional divisions for those layers, but in general include a lower layer commonly referred to as the “network layer” in which routing functions reside. A connection through a network may pass through intermediate network nodes, such as routers, whose highest implemented layer is often the network layer.
IBM's Advanced Peer-to-Peer Network (“APPN”) is an example of a layered computer network architecture in which the nodes of the network are peers. That is, each node is considered to be an equal to all other nodes from a control perspective.
In many cases, the links between nodes in a network are actually logical connections provided by an “underlying network”. An underlying network is a portion of a network made up of physical nodes and links which are reachable using a common protocol and/or a common transmission medium. For example, many links in SNA or TCP/IP networks are actually comprised of underlying networks which use protocols such as Ethernet, Frame Relay, or Asynchronous Transfer Mode (“ATM”). An underlying network provides services that are used to create logical links at the network layer.
The APPN architecture uses “Topology Routing Services” to share route and topology information. By definition, a topology subnetwork shares routing and topology information among its own network nodes, but this information is not shared with nodes outside the topology subnetwork. Therefore, while a border node in one topology subnetwork may be aware of a link address to a border node in an adjacent topology subnetwork, it has no other information about the topology of that adjacent topology subnetwork.
The underlying networks, while constructed from nodes and links like the networks, may have very different capabilities. Underlying networks may use different location protocols and different routing protocols, and may transmit data in different data packet formats. The functionality provided for nodes at the underlying network layer (sometimes referred to as the “data link” layer or “data link control” layer) is often unaware of the higher layer protocols, and in particular of the network layer protocols. Similarly, the network layer functionality may have minimal knowledge of the underlying network.
Routing protocols can take advantage of knowledge that two nodes are connected via an underlying network, and can use this knowledge to set up a logical link or path between these two nodes through the underlying network without requiring the path to be routed through any network nodes. An example scenario is illustrated in FIG. 1, where end node 100, which is located on token ring LAN segment 110, may communicate with end node 150 which is located on a different token ring LAN segment 160, without requiring the data path to be routed through either of network nodes 120, 170. Initially, a route from node 100 to node 150 may be calculated as passing through network node 120, and then to bridge 140, and from there to network node 170 after which the path ends with node 150. However, if the LAN segments 110 and 160 have been defined as being connected to the same “virtual routing node” or “VRN”, then the route may be compressed such that node 100 directly addresses node 150. A VRN is an abstract representation of the underlying network which may be used for route calculation purposes. Using the compressed route, the data packets sent by node 100 use node 150 as the destination address. When the packets reach bridge 140, the bridge detects that the packets need to be transferred to LAN segment 160. Node 150 then sees that it is the destination of the packets, and removes them from the ring. A technique which may be used to implement this avoidance of the network nodes for the data transmission path was disclosed in commonly-assigned U.S. Pat. No. 5,943,317, which is entitled “Sub-network Route Optimization Over a Shared Access Transport Facility” (hereinafter “the route optimization patent”), which is hereby incorporated herein by reference as if set forth fully.
The route optimization patent applies to underlying networks wherein a common connection network, referred to therein as a “shared access transport facility” or “SATF”, exists. An SATF is a communications medium that can be shared among users simultaneously. Examples include a token ring LAN and an Ethernet LAN, where use of collision detection and/or collision avoidance protocols allows the nodes on the LAN to share the medium for transmitting and receiving packets. Other examples of SATFs include X.25 networks, Frame Relay networks, and ATM networks where underlying network switches provide the arbitration necessary to permit simultaneous use.
In APPN networks, nodes which identify their connectivity to the SATF by a common virtual routing node communicate efficiently between one another even though they do not have individually defined connections to one another. (For example, with reference to FIG. 1, node 100 does not have a defined connection to node 150, yet it can communicate directly with node 150 using the techniques disclosed in the route optimization patent.) “Dual network” nodes—that is, nodes (which may be end nodes, network nodes, or border nodes) that participate in both the network and underlying network—are used for transmission and routing in the combined network, but the distributed routing protocols at the network and underlying network layer are effectively isolated from each other with this approach.
As stated earlier, networks of nodes and links may be interconnected through border nodes. The Border Gateway Protocol, or “BGP”, defined in RFC 1771, “A Border Gateway Protocol 4 (BGP-4)”, (March 1995), is a routing protocol that enables network-to-network communication by exchanging information through gateway nodes which are located at the border of each network. An “extended border node” or “EBN” is a border node implemented according to “APPN Extended Border Node Architecture Reference”, IBM Publication SV40-0128-00. Hereinafter, the terms “border node” and “extended border node” are used interchangeably.
Border nodes allow location protocols to pass through to other topology subnets, in order to search for a particular destination node. (A “topology subnet”, as the term is used herein, refers to a group of APPN network nodes that share a common topology database and participate with each other in the APPN topology and routing services protocols.) The EBNs then obtain information to be used in calculating a route to that node, and propagate this information backwards along the location protocol's path until reaching the network node from which the locate request message of the location protocol originated. FIG. 2 illustrates an example scenario where end node 200 in a first APPN network 210 requests a connection to end node 260 in a second APPN network 270. End node 260 reports information on its own address and its TG 255 to network node 250. Border node 240 obtains information on how to reach network node 250 (e.g. by consulting a topology database for network 270), and concatenates that information to the TG 255 and addressing information for end node 260. The border node then sends the information it obtained backwards along the path of the locate request message, as a locate response message. In this prior art process, one of the two EBNs at each network boundary is required to provide the other EBN a list of the links between them so that the other EBN knows which links to use to compute the data transmission path. In the example of FIG. 2, to cross between network 210 and network 270, EBN 240 is required to pass information regarding TG 235 to EBN 230.
Once the location protocol information is returned to network node 220, the network node then obtains end node 200's address and connectivity information regarding TG 205, and concatenates this to the path information returned in the locate response message. This concatenated path may be represented abstractly as:                EN 200–TG 205–NN 220–TG 225–EBN 230–TG 235–EBN 240–TG 245–NN 250–TG 255–EN 260        
Route optimization is applied to this route as it is constructed. For example, the path need not traverse NNs such as 220 and 250 if there are other links or underlying networks available. However, the path must always traverse EBN 230 and EBN 240.
FIG. 3 shows an abstract representation of this prior art route selection approach, wherein the path used by the location protocol to locate end node 260 is shown using a dashed line as the upper path 310. Note that this path 310 traverses both networks 210 and 270, as described with reference to FIG. 2. The same route selection algorithm is used in each network to select a piece of the end-to-end path, and these pieces are then connected by the border nodes. The data transmission path which may result is shown using a solid line as the lower path 320. This figure illustrates that the data transmission path 320 within each network may be optimized and need not follow the same route as the location protocol. In particular, the data transmission path 320 may take full advantage of the connectivity of end node 200 and EBN 230 to underlying network 330, and of EBN 240 and end node 260 to underlying network 340. However, the data transmission path 320 may not bypass the EBNs 230, 240 through which the location protocol traversed. This is so even if underlying networks 330 and 340 are the same underlying network, such as the public Internet or other commonly-addressable collection of nodes and links. As a result, the data transmission path 320 is not truly optimized in many cases. (Furthermore, a data transmission path computed in this manner is not sufficiently flexible to avoid outages and/or network congestion that may occur at the EBNs.)
Additional drawbacks of prior art cross-network routing occur when the data transmission path crosses several networks. An example is illustrated in FIG. 4, where a path from end node 410 to end node 490 is needed. The location protocol in this example sends a locate request message from network 420 through EBN 430, to EBN 440 and then through network 450 to EBN 460. EBN 460 forwards the locate request message to an EBN in another network, such as EBN 470 which is located at the boundary of network 480. As the results of the location protocol are assembled and sent back along the location protocol's path, for example from EBN 470 to EBN 460 and so forth, the data structures used to store the concatenated route information may become quite large. A composite route selection sub-vector (“CRSS”) for the path through the border nodes is stored within the locate response message when using APPN, and contains the routing information to span more than one sub-network. The CRSS has a maximum size of 256 bytes. If the routing information in this CRSS becomes too large, then the CRSS is removed. However, removing the CRSS means that route optimizations (such as the route compression technique defined in the route optimization patent) cannot be performed, and this is therefore an undesirable situation.
Accordingly, what is needed is an improved technique for routing data across multiple topology subnets which avoids the problems of the prior art.